package medium;

import java.util.Arrays;

/**
 * 2952. 需要添加的硬币的最小数量
 * 创建时间：2024-03-30 21:22
 * 地址：https://leetcode.cn/problems/minimum-number-of-coins-to-be-added/description/
 */
public class 需要添加的硬币的最小数量_2952 {
    static class Solution {
        public int minimumAddedCoins(int[] coins, int target) {
            Arrays.sort(coins);
            int ans = 0;
            int s = 1; // 一开始只能组成[0, s-1]的所有整数
            int i = 0;
            int l = coins.length;
            // 当s-1 >= target时，表示[1, target]，循环结束
            while(s <= target) {
                // 解释：为什么coins[i] <= s
                // 设x = coins[i]，[0, s-1] + x = [x, s + x - 1]
                // 当 [0, s-1]和[x, s + x - 1]缺少的数字，就是需要补充的数字
                // 当 两个区间可以合并，就表示两个区间合并后是连续的，此时要满足 s >= x
                if (i < l && coins[i] <= s) {
                    s += coins[i];
                    i++;
                } else {
                    s *= 2;
                    ans++;
                }
            }
            return ans;
        }
    }
}
